设 表示由 走到 的期望步数。
那么显然有转移:
其中 分别表示 向上/下/左/右走的概率。
边界条件:
然后你发现它们互相有依赖,不能直接转移,所以直接高斯消元。
但这样时间复杂度是 ,考虑优化
- 因为每一个方程不为 的系数最多 个,所以增广矩阵其实很稀疏,系数为 就不需要加减消元了。
- 我们只需要 ,所以消成下三角矩阵就可以了。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-16
const int MAXN = 50;
int n , m , fn;
double a[ MAXN * MAXN + 5 ][ MAXN * MAXN + 5 ];
void Gauss( ) {
for( int i = fn ; i >= 1 ; i -- ) {
for( int j = i - 1 ; j >= 1 ; j -- ) {
double t = a[ j ][ i ] / a[ i ][ i ];
if( fabs( t ) < eps ) continue;
for( int k = i ; k >= 1 ; k -- )
a[ j ][ k ] -= t * a[ i ][ k ];
a[ j ][ fn + 1 ] -= t * a[ i ][ fn + 1 ];
}
}
}
pair< int , int > dir[ 4 ] = { { 1 , 0 } , { 0 , 1 } , { -1 , 0 } , { 0 , -1 } };
double p[ MAXN + 5 ][ MAXN + 5 ][ 4 ];
int Hash( int x , int y ) {
if( x < 1 || x > n || y < 1 || y > m ) return fn + 2; //越界
return ( x - 1 ) * m + y;
}
int main( ) {
while( scanf("%d %d",&n,&m) && ( n + m ) ) {
fn = n * m;
for( int k = 0 ; k < 4 ; k ++ )
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ )
scanf("%lf",&p[ i ][ j ][ k ]);
memset( a , 0 , sizeof( a ) );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= m ; j ++ ) {
int h = Hash( i , j );
a[ h ][ h ] = -1;
if( i == n && j == m ) continue;
a[ h ][ fn + 1 ] = -1;
for( int k = 0 ; k < 4 ; k ++ )
a[ h ][ Hash( i + dir[ k ].first , j + dir[ k ].second ) ] = p[ i ][ j ][ k ];
}
Gauss( );
printf("%.1f\n", a[ 1 ][ fn + 1 ] / a[ 1 ][ 1 ] );
}
return 0;
}